package com.wxit.algorithm.stack;

import java.util.LinkedList;

/**
 * 中缀表达式转后缀表达式
 */
public class InfixToSuffix {

    public static void main(String[] args) {
        System.out.println(infixToSuffix("a+b"));
        System.out.println(infixToSuffix("a*b+c"));
        System.out.println(infixToSuffix("(a+b)*c-d"));
    }

    static int priority(char c) {
        return switch (c) {
            case '*', '/' -> 2;
            case '+', '-' -> 1;
            case '(' -> 0;
            default -> throw new IllegalArgumentException("未知运算符" + c);
        };
    }

    /**
     * 1.遇到非运算符，直接拼串
     * 2.遇到 + - * /
     *      1.比较优先级，比栈顶的优先级高，直接入栈
     *      2.比栈顶的优先级低，把栈里优先级 》= 它的都出栈，它在入栈
     *  3.遍历完成，栈里剩余运算符依次出栈
     * @param infix
     * @return
     */
    static String infixToSuffix(String infix) {
        LinkedList<Character> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder(infix.length());
        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);
            switch (c) {
                case '*', '/', '+', '-' -> {
                    if (stack.isEmpty()) {
                        stack.push(c);
                    } else {
                        if (priority(c) > priority(stack.peek())) {
                            stack.push(c);
                        } else {
                            while(!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
                                sb.append(stack.pop());
                            }
                            stack.push(c);
                        }
                    }
                }
                case '(' -> {
                    stack.push(c);
                }
                case ')' -> {
                    while (!stack.isEmpty() && stack.peek() != '(') {
                        sb.append(stack.pop());
                    }
                    stack.pop();
                }
                default -> {
                    sb.append(c);
                }
            }
        }
        while (!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();
    }
}
